﻿/*
E-必做 表达式求值
分数 30
作者 朱允刚
单位 吉林大学
给定一个中缀表达式，请编写程序计算该表达式的值。表达式包含+、-、*、\、^、(、)，所有运算均为二元运算，操作数均为正整数，但可能不止一位，不超过10位。运算结果为整数，值域为[−231,231)。除法运算结果若为小数则进行截尾取整。若除法运算中除数为0，则输出INVALID。幂运算须自行实现，不允许调用pow等系统函数。测试数据保证幂运算中指数为非负，底数不为0。

输入格式:
输入为多行，每行为一个长度不超过1000的字符串，表示中缀表达式。

输出格式:
对每个表达式输出一行：为一个整数（表达式的值）或为一个字符串INVALID。

输入样例:
5+(10*2)-6
8*(999+1)
1+5/(1-1)
7*2^3

输出样例:
19
8000
INVALID
56
代码长度限制
16 KB
时间限制
50 ms
内存限制
64 MB
*/

#include <iostream>
#include <stack>
#include <cctype>  // 用于判断字符类型

using namespace std;

// 计算幂运算的函数
int power(int base, int exponent) {
    int result = 1;
    for (int i = 0; i < exponent; ++i) {
        result *= base;
    }
    return result;
}

// 判断运算符的优先级
int getPriority(char op) {
    if (op == '^') {
        return 3;
    }
    else if (op == '*' || op == '/') {
        return 2;
    }
    else if (op == '+' || op == '-') {
        return 1;
    }
    else {
        return 0;
    }
}

// 执行运算的函数
int performOperation(char op, int operand1, int operand2) {
    switch (op) {
    case '+':
        return operand1 + operand2;
    case '-':
        return operand1 - operand2;
    case '*':
        return operand1 * operand2;
    case '/':
        if (operand2 == 0) {
            cout << "INVALID" << endl;
            exit(0);
        }
        return operand1 / operand2;
    case '^':
        return power(operand1, operand2);
    default:
        return 0;  // 不会执行到这里，只是为了避免编译器警告
    }
}

// 中缀表达式求值的函数
int evaluateExpression(const string& expression) {
    stack<int> operands;
    stack<char> operators;

    for (char token : expression) {
        if (isdigit(token)) {
            operands.push(token - '0');
        }
        else if (token == '(') {
            operators.push(token);
        }
        else if (token == ')') {
            while (!operators.empty() && operators.top() != '(') {
                char op = operators.top();
                operators.pop();

                int operand2 = operands.top();
                operands.pop();

                int operand1 = operands.top();
                operands.pop();

                operands.push(performOperation(op, operand1, operand2));
            }
            operators.pop();  // 弹出左括号
        }
        else {
            while (!operators.empty() && getPriority(operators.top()) >= getPriority(token)) {
                char op = operators.top();
                operators.pop();

                int operand2 = operands.top();
                operands.pop();

                int operand1 = operands.top();
                operands.pop();

                operands.push(performOperation(op, operand1, operand2));
            }
            operators.push(token);
        }
    }

    while (!operators.empty()) {
        char op = operators.top();
        operators.pop();

        int operand2 = operands.top();
        operands.pop();

        int operand1 = operands.top();
        operands.pop();

        operands.push(performOperation(op, operand1, operand2));
    }

    return operands.top();
}

int main() {
    string expression;
    while (cin >> expression) {
        int result = evaluateExpression(expression);
        cout << result << endl;
    }

    return 0;
}
/*
这个程序中，evaluateExpression函数使用两个栈，一个用于存储操作数，另一个用于存储运算符。遍历表达式，根据当前字符的类型进行相应的处理。运算符的优先级通过getPriority函数判断。performOperation函数用于执行具体的运算。最后，将结果从操作数栈中弹出即可。

注意：程序中使用了exit(0)语句来终止程序执行，这是因为在除法运算中，如果除数为0，会输出"INVALID"并终止程序。
*/